#include<iostream>
using namespace std;

const int SIZE1 = 10;
int arr[SIZE1] = {47, 38, 65, 97, 76, 13, 27, 49, 55, 4};
int rec[SIZE1] = { 0 };

void merge(int fir, int end, int mid);
int pass(int n);
void mergeSort3(int n);

void mergeSort3(int n)
{
	int num = pass(n);
	while (num != 2)
	{
		for (int i = 0; i < num; i += 2)
		{
			merge(rec[i], rec[i+2]-1, rec[i+1]-1);
		}
		num = pass(n);
	}
}

void merge(int fir, int end, int mid)
{
	int tempArr[SIZE1];
	int fir1 = fir, fir2 = mid + 1;
	for (int i = fir; i <= end; ++i)
	{
		if (fir1 > mid)
			tempArr[i] = arr[fir2++];
		else if (fir2 > end)
			tempArr[i] = arr[fir1++];
		else if (arr[fir1] > arr[fir2])
			tempArr[i] = arr[fir2++];
		else
			tempArr[i] = arr[fir1++];
	}

	for (int i = fir; i <= end; ++i)
		arr[i] = tempArr[i];
}

int pass(int n)
{
	int num = 0;
	int biger = arr[0];
	rec[num++] = 0;
	for (int i = 1; i < n; i++)
	{
		if (arr[i] >= biger)
			biger = arr[i];
		else
		{
			rec[num++] = i;
			biger = arr[i];
		}
	}

	rec[num++] = n;
	return num;
}

int main()
{
	mergeSort3(10);

	for (int i = 0; i < 10; i++)
		cout << arr[i] << " ";
	cout << endl;

	return 0;
}